class Solution {
public:
    int calculateMinimumHP(std::vector<std::vector<int>>& dungeon) {
        int minHP = INT_MIN;
        int row = dungeon.size();
        int col = dungeon[0].size();
        int tmp;
        if(dungeon[row-1][col-1]>0) dungeon[row-1][col-1] = 0;
        
        for(int i = row -2;i >= 0; --i){                
            dungeon[i][col-1] = dungeon[i][col-1] > 0 ? min(dungeon[i][col-1]+ dungeon[i+1][col-1],0) : dungeon[i][col-1]+ dungeon[i+1][col-1];            
        }
        
        for(int j = col - 2;j >=0 ; --j){
            dungeon[row - 1][j] = dungeon[row-1][j] > 0 ? min(dungeon[row-1][j] + dungeon[row-1][j+1],0) : dungeon[row-1][j] + dungeon[row-1][j+1]; 
        }
        
        for(int i = row - 2;i >= 0; --i){
            for(int j = col - 2;j >= 0; --j){
                dungeon[i][j] = dungeon[i][j] > 0 ?
                            min(max(dungeon[i+1][j], dungeon[i][j+1]) + dungeon[i][j],0) :
                            max( dungeon[i+1][j] , dungeon[i][j+1] ) + dungeon[i][j];
            }
        
        }
        
        return -dungeon[0][0] + 1;        
    }
    
    void printVectorInt(std::vector<std::vector<int>>& dungeon){
        int row = dungeon.size();
        int col = dungeon[0].size();
        for(int i = 0;i < row;++i){
            for(int j = 0;j<col;++j){
                std::cout<<dungeon[i][j]<<'\t';
            }
            std::cout<<std::endl;
        }
    }
};